package leetcode.weekly.week345;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//Solution4Test
public class Solution4 {

	int[] p;
	int[] cnts;

	public void init(int size) {
		p = new int[size];
		cnts = new int[size];
		for (int i = 0; i < p.length; i++) {
			p[i] = i;
		}
		Arrays.fill(cnts, 1);
	}

	public void union(int a, int b) {
		int A = find(a), B = find(b);
		if (A == B)
			return;
		p[A] = B;
		cnts[B] += cnts[A];
		cnts[A] = 0;
	}

	public int find(int id) {
		if (p[id] != id) {
			p[id] = find(p[id]);
		}
		return p[id];
	}

	public int countCompleteComponents(int n, int[][] edges) {
		List<List<Integer>> nexts = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			nexts.add(new ArrayList<>());
		}
		int m = edges.length;
		int[] ins = new int[n];
		for (int i = 0; i < m; i++) {
			int u = edges[i][0], v = edges[i][1];
			nexts.get(u).add(v);
			nexts.get(v).add(u);
			ins[u]++;
			ins[v]++;
		}
		init(n);
		for (int i = 0; i < n; i++) {
			List<Integer> next = nexts.get(i);
			for (int j : next) {
				union(i, j);
			}
		}
		int ans = 0;
		Set<Integer> done = new HashSet<>();
		for (int i = 0; i < n; i++) {
			int pi = find(i);
			if (done.add(pi)) {
				int need = cnts[pi] - 1;
				if (ins[i] == need) {
					boolean ok = true;
					List<Integer> next = nexts.get(i);
					for (int j : next) {
						if (ins[j] != need) {
							ok = false;
							break;
						}
					}
					if (ok)
						ans++;
				}
			}
		}
		return ans;
	}
}
